package shortestDistanceAfterQueries;

import java.util.ArrayList;
import java.util.List;

public class DpSolution {

    /**
     * 动态规划
     * @param n 终点
     * @param queries 图的边界
     * @return 最短路径
     */
    public int[] shortestDistanceAfterQueries(int n, int[][] queries) {

        //记录到达每个终点i的所有起点
        List<List<Integer>> starts = new ArrayList<>();
        // 记录动态规划的过程
        int[] dp = new int[n];
        for (int i = 0; i < n; i+=1) {
            List<Integer> s = new ArrayList<>();
            s.add(i-1);
            starts.add(s);
            dp[i] = i;
        }


        int[] res = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            //更新图的起点
            starts.get(queries[i][1]).add(queries[i][0]);
            //计算从i->n
            for (int j = queries[i][1]; j <n ; j++) {
                List<Integer> cur = starts.get(j);
                for (Integer st : cur) {
                    dp[j] = Math.min(dp[j], dp[st] +1);
                }
            }
            res[i] = dp[n-1];
        }
        return  res;
    }

}
